package com.jiang.专题.动态规划.Q647;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/04/18 15:42
 */
public class Solution {
    // 动态规划
//    public int countSubstrings(String s) {
//        char[] chars = s.toCharArray();
//        int n = chars.length;
//        boolean[][] dp = new boolean[n][n];
//        int res = n; // 初始化为字符串长度，因为每个字符本身就是一个回文串
//        for (int i = n - 1; i >= 0; i--) {
//            for (int j = i + 1; j < n; j++) {
//                if (chars[i] == chars[j]) {
//                    if (j - i < 3) { // 当j-i<3时，即回文子串长度为2或3，直接判断
//                        dp[i][j] = true;
//                    } else {
//                        dp[i][j] = dp[i + 1][j - 1];
//                    }
//                    if (dp[i][j]) {
//                        res++;
//                    }
//                }
//            }
//        }
//        return res;
//    }

    // 中心扩散（1）
//    public int countSubstrings(String s) {
//        int n = s.length(), ans = 0;
//        for (int i = 0; i < 2 * n - 1; ++i) {
//            int l = i / 2, r = i / 2 + i % 2;
//            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
//                --l;
//                ++r;
//                ++ans;
//            }
//        }
//        return ans;
//    }

    // 中心扩散（2）
    int num = 0;
    public int countSubstrings(String s) {
        for (int i=0; i < s.length(); i++){
            count(s, i, i);//回文串长度为奇数
            count(s, i, i+1);//回文串长度为偶数
        }
        return num;
    }

    public void count(String s, int start, int end){
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            num++;
            start--;
            end++;
        }
    }
}
